#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Graph
{
    int x, y, r;
};

int bfs(vector<vector<int>> &grid, int k)
{
    int m = grid.size(), n = grid[0].size();
    if (m == 1 & n == 1)
        return 0;
    k = min(k, m + n - 3);

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    vector<vector<vector<bool>>> vis(m, vector<vector<bool>>(n, vector<bool>(k + 1, false)));
    queue<Graph> q;
    q.emplace(Graph{0, 0, k});
    vis[0][0][k] = true;
    int step = 0;
    while (!q.empty())
    {
        Graph c = q.front();
        q.pop();
        step++;
        for (int i = 0; i < 4; ++i)
        {
            int x = c.x + dx[i];
            int y = c.y + dy[i];
            int r = c.r;
            if (x >= 0 && x < m && y >= 0 && y < n)
            {
                if (x == m - 1 && y == n - 1) return step;
                if (grid[x][y] == 0 && !vis[x][y][r])
                {
                    q.emplace(Graph{x, y, r});
                    vis[x][y][r] = 1;
                }
                else if (grid[x][y] == 1 && r > 0 && !vis[x][y][r - 1])
                {
                    q.emplace(Graph{x, y, r - 1});
                    vis[x][y][r - 1] = 1;
                }
            }
        }
    }
    return -1;
}

int main()
{
    return 0;
}